import java.util.Iterator;
public class RandomQueue<Item> implements Iterable<Item>
{

	private Item[] s, temp;
	private int N = 0;

	@SuppressWarnings("unchecked")
	public RandomQueue() {
		s = (Item[]) new Object[N + 1]; // Empty array with room for one Item
	}

	public boolean isEmpty() {
		return N == 0;
	}

	public int size() {
		return N;
	}

	@SuppressWarnings("unchecked")
	public void enqueue(Item item) {
		s[N++] = item;
		if (s.length == N){
			temp = s;
			s = (Item[]) new Object[N * 2];
			for (int i = 0; i < temp.length; i++) s[i] = temp[i];}
	}

	public Item sample() {
		if (isEmpty()) throw new RuntimeException();
		return s[StdRandom.uniform(N)];
	}

	public Item dequeue() {
		if (isEmpty()) throw new RuntimeException();
		temp = s;
		int random = StdRandom.uniform(N--);
		for (int i = 0; i < temp.length; i++) if (i != random) s[i] = temp[i];
		return s[StdRandom.uniform(N)];
	}

	@Override
	public Iterator<Item> iterator() {
		return new ArrayIterator();
	}

	private class ArrayIterator implements Iterator<Item>
	{
		private int i = N;
		private Item[] temp = s.clone();
		
		public boolean hasNext() { return i > 0; }

		public void remove() { /* not supported */ }

		public Item next() {
			int random = StdRandom.uniform(i);
			Item nextItem = temp[random];
			temp[random] = temp[i-1];
			temp[i-1] = nextItem;
			i--;
			return nextItem;
		}
	}

	public static void main(String args[])
	{
		// Build a queue containing the Integers 1,2,...,6:
		RandomQueue<Integer> Q= new RandomQueue<Integer>();
		for (int i = 1; i < 7; ++i) Q.enqueue(i); // autoboxing! cool!

		// Print 30 die rolls to standard output
		StdOut.print("Some dice rolls: ");
		for (int i = 1; i < 30; ++i) StdOut.print(Q.sample() +" ");
		StdOut.println();

		// Let's be more serious: do they really behave like die rolls?
		int[] rolls= new int [10000];
		for (int i = 0; i < 10000; ++i)
			rolls[i] = Q.sample(); // autounboxing! Also cool!
		StdOut.printf("Mean (should be around 3.5): %5.4f\n", StdStats.mean(rolls));
		StdOut.printf("Standard deviation (should be around 1.7): %5.4f\n",
				StdStats.stddev(rolls));

		// Let's look at the iterator. First, we make a queue of colours:

		RandomQueue<String> C= new RandomQueue<String>();
		C.enqueue("red"); C.enqueue("blue"); C.enqueue("green"); C.enqueue("yellow"); 

		Iterator I= C.iterator();
		Iterator J= C.iterator();

		StdOut.print("Two colours from first shuffle: ");
		StdOut.print(I.next()+" ");
		StdOut.print(I.next()+" ");

		StdOut.print("\nEntire second shuffle: ");
		while (J.hasNext()) StdOut.print(J.next()+" ");

		StdOut.print("\nRemaining two colours from first shuffle: ");
		StdOut.print(I.next()+" ");
		StdOut.println(I.next());
	}

}